package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 快照数组
 */

public class Code1146 {
    public static void main(String[] args) {
        SnapshotArray snapshotArray = new Code1146().new SnapshotArray(3);
        snapshotArray.set(0, 5);
        System.out.println(snapshotArray.snap());
        snapshotArray.set(0, 6);
        System.out.println(snapshotArray.snap());
        System.out.println(snapshotArray.get(0, 0));
        System.out.println(snapshotArray.get(0, 1));
        System.out.println(snapshotArray.get(1, 1));
        System.out.println(snapshotArray.get(0, 1));
    }

    class SnapshotArray {
        private int snap_id = 0;
        private List<List<Node>> list;

        class Node {
            public int value;
            public int snap_id;

            public Node(int value, int snap_id) {
                this.value = value;
                this.snap_id = snap_id;
            }
        }

        public SnapshotArray(int length) {
            list = new ArrayList<>(length);
            for (int i = 0; i < length; i++) {
                list.add(new ArrayList<>());
                list.get(i).add(new Node(0, 0));
            }
        }

        public void set(int index, int val) {
            Node node = list.get(index).get(list.get(index).size() - 1);
            if (node.snap_id == snap_id) {
                node.value = val;
                return;
            }
            list.get(index).add(new Node(val, snap_id));
        }

        public int snap() {
            return snap_id++;
        }

        public int get(int index, int snap_id) {
            List<Node> nodes = list.get(index);
            int pos = lowerBound(nodes, snap_id + 1) - 1;
            return nodes.get(pos).value;
        }

        private int lowerBound(List<Node> nodes, int target) {
            int left = -1, right = nodes.size(), mid;
            while (left + 1 < right) {
                mid = left + (right - left) / 2;
                if (nodes.get(mid).snap_id >= target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        }
    }
}
